package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 90. 子集 II
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 * 示例 2：
 *
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 * @author SHM
 */
public class SubsetsWithDup {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(false, 0, nums);
        return ans;
    }

    /**
     * 方法二：递归法实现子集枚举
     * 思路
     *
     * 与方法一类似，在递归时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。
     * 复杂度分析
     *
     * 时间复杂度：O(n \times 2^n)O(n×2
     * n
     *  )，其中 nn 是数组 \textit{nums}nums 的长度。排序的时间复杂度为 O(n \log n)O(nlogn)。最坏情况下 \textit{nums}nums 中无重复元素，需要枚举其所有 2^n2
     * n
     *   个子集，每个子集加入答案时需要拷贝一份，耗时 O(n)O(n)，一共需要 O(n \times 2^n)+O(n)=O(n \times 2^n)O(n×2
     * n
     *  )+O(n)=O(n×2
     * n
     *  ) 的时间来构造子集。由于在渐进意义上 O(n \log n)O(nlogn) 小于 O(n \times 2^n)O(n×2
     * n
     *  )，故总的时间复杂度为 O(n \times 2^n)O(n×2
     * n
     *  )。
     *
     * 空间复杂度：O(n)O(n)。临时数组 \textit{t}t 的空间代价是 O(n)O(n)，递归时栈空间的代价为 O(n)O(n)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/subsets-ii/solution/zi-ji-ii-by-leetcode-solution-7inq/
     * @param choosePre
     * @param cur
     * @param nums
     */
    public void dfs(boolean choosePre, int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
            return;
        }
        t.add(nums[cur]);
        dfs(true, cur + 1, nums);
        t.remove(t.size() - 1);
    }
}
